package class3;

import common.ListNode;
import common.ListNodeUtils;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/palindrome-linked-list/description/
 * 判断一个链表是否为回文结构
 * 实例：
 * 1 -> 2 -> 2 -> 1 true
 * 1 -> 2 -> 3 -> 2 -> 1 true
 * 1 -> 2 -> 3 -> 4 false
 * 解题思路：
 * 1.利用stack的特性。入栈和出栈比较
 * 2.部分压栈，只压链表右半部分
 *
 *
 */
public class Code14_isPalindrome {
    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(1, 2, 3, 4, 3, 2, 1);
        boolean palindrome = isPalindrome(head);
        System.out.println("palindrome = " + palindrome);

        boolean palindrome2 = isPalindrome2(head);
        System.out.println("palindrome2 = " + palindrome2);

        boolean palindrome3 = isPalindrome3(head);
        System.out.println("palindrome3 = " + palindrome3);
    }

    /**
     * 解法1：
     * 操作步骤：
     * 1.将[1 2 3 2 1]压入栈中，
     * 2.再次遍历链表 并与 弹出的栈顶 依次进行比较
     * 3.如果数值不相同，则不为会问结构
     */
    public static boolean isPalindrome(ListNode head) {

        ListNode cur = head;
        Stack<ListNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (head != null) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /***
     *
     * 与方法1相似，但利用快慢指针，仅把右侧的数据压栈，然后出栈进行比较
     */
    public static boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head; // 中间节点
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        Stack<ListNode> stack = new Stack<>();
        while (slow != null) {
            stack.push(slow);
            slow = slow.next;
        }
        if (!stack.isEmpty()) {
            while (!stack.isEmpty()) {
                if (head.val != stack.pop().val) {
                    return false;
                }
                head = head.next;
            }
        }
        return true;
    }

    /**
     * 性能较好，推荐
     * 不利用栈
     * 利用快慢指针，将中间节点右侧的链表进行反转，然后再进行比较
     */
    public static boolean isPalindrome3(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 此时slow已经走到链表中部
        ListNode newHead = slow.next; // 右半边的其实节点
        slow.next = null;
        ListNode next;
        ListNode pre = slow; // 反转时，右边链表的pre节点要赋值 中间节点 slow
        // 右半边反转
        while (newHead != null) {
            next = newHead.next;
            newHead.next = pre;
            pre = newHead;
            newHead = next;
        }

        ListNode l = head;
        ListNode r = pre;
        boolean res = true;
        // 比较两个节点的值是否相同
        while (pre != null && l != null) {
            if (pre.val != l.val) {
                res = false;
                break;
            }
            pre = pre.next;
            l = l.next;
        }
        ListNode p = null;
        while(r!=null){
            next = r.next;
            r.next = p;
            p = r;
            r = next;
        }
        return res;

    }
}
